package com.cdy.demo.algorithm;

public class Leetcode474 {

    public static void main(String[] args) {

    }

    /**
     * 474  挑选符合0，1最大个数的最大集合数量
     * @param strs
     * @param m
     * @param n
     * @return
     */
    public int findMaxForm(String[] strs, int m, int n) {
        int length = strs.length;
        int[][][] dp = new int[length + 1][m + 1][n + 1];
        for (int i = 0; i < length + 1; i++) {
            if (i == 0) {
                continue;
            }
            int[] num = getNum(strs[i - 1]);

            for (int j = 0; j < m + 1; j++) {
                for (int k = 0; k < n + 1; k++) {
                    if (j >= num[0] && k >= num[1]) {
                        dp[i][j][k] = Math.max(dp[i - 1][j][k], dp[i-1][j - num[0]][k - num[1]]+ 1) ;
                    } else {
                        dp[i][j][k] = dp[i - 1][j][k];
                    }
                }
            }

        }
        return dp[length][m][n];
    }

    private int[] getNum(String str) {
        int[] num = new  int[2];
        for (char c1 : str.toCharArray()) {
            num[c1 - '0']++;
        }
        return num;
    }
}
